homework 3, version 0

Submission by: Jazzy Doe (jazz@mit.edu)

Homework 3: Structure and Language

18.S191, fall 2020

This notebook contains built-in, live answer checks! In some exercises you will see a coloured box, which runs a test case on your code, and provides feedback based on the result. Simply edit the code, run it, and the check runs again.

For MIT students: there will also be some additional (secret) test cases that will be run as part of the grading process, and we will look at your notebook and write comments.

Feel free to ask questions!

Let's create a package environment:

Exercise 1: Language detection

In this exercise, we are going to create some super simple Artificial Intelligence. Natural language can be quite messy, but hidden in this mess is structure, which we are going to look for today.

Let's start with some obvious structure in English text: the set of characters that we write the language in. If we generate random text by sampling random Unicode characters, it does not look like English:

Instead, let's define an alphabet, and only use those letters to sample from. To keep things simple, we ignore punctuation, capitalization, etc, and only use these 27 characters:

Let's sample random characters from our alphabet:

That alreay looks a lot better than our first attempt! But still, this does not look like English text - we can do better.

English words are not well modelled by this random-latin-characters-model. Our first observation is that some letters are more common than others. To put this observation into practice, we would like to have the frequency table of the latin alphabet. We can search for it online, but it is actually very simple to calculate ourselves! The only thing we need is a representative sample of English text.

The following samples are from Wikipedia, but feel free to type in your own sample! You can also enter a sample of a different language, if that language can be expressed in the latin alphabet.

Remeber that the button on the left of a cell will show or hide the code.

We also include a sample of Spanish, we'll use it later!

Exercise 1.1 - Cleaning data

Looking at the sample, we see that it is quite messy - it contains punctiation, accented letters and numbers. For our analysis, we are only interested in our 27-character alphabet (i.e. 'a' through 'z' plus ' '). We are going to clean the data using the Julia function filter.

filter takes two arguments: a function and a collection. The function is applied to each element of the collection, and it returns either true or false. If the result is true, then that element ends up in the final collection.

Did you notice something cool? Functions are also just objects in Julia, and you can use them as arguments to other functions! (Fons thinks this is super cool.)

We have written a function isinalphabet, which takes a character, and returns a boolean:

👉 Use filter to extract a just the characters from our alphabet out of messy_sentence.

We are not interested in the case of letters ('A' vs 'a'), so we want to map these to lowercase before we apply our filter. If we don't, all uppercase letters get deleted.

👉 Use the function lowercase to convert messy_sentence_2 into a lowercase string, and then use filter to extract only the characters from our alphabet.

Finally, we need to deal with accents - simply deleting accented charactersfrom the source text might deform it too much. We can add accented letters to our alphabet, but a simpler solution is to replace accented letters with the unaccented base character. We have written a function unaccent that does just that.

👉 Let's put everything together. Write a function clean that takes a string, and returns a cleaned version, where:

• accented letters replaced by their base characters

• uppercase converted to lowercase

• filtered to only contain characters from alphabet

Exercise 1.2 - Letter frequencies

We are going to count the frequency of each letter in this sample, after applying your clean function. Can you guess which character is most frequent?

The result is a 27-element array, with values between 0.0 and 1.0. These values correspond to the frequency of each letter.

sample_freqs[i] == 0.0 means that the $i$th letter did not occur in your sample, and sample_freqs[i] == 0.1 means that 10% of the letters in the sample are the $i$th letter.

To make it easier to convert between a character from the alphabet and its index, we have the following function:

👉 Which letters from the alphabet did not occur in the sample?

Now that we know the frequencies of letters in English, we can generate random text that already looks closer to English!

Random letters from the alphabet:

iazgtzagm hmjjwpihjsqposwivee ajfefbsgkgnvppsx juhelegoncoyslrkgcqnfvbqitxbxvevoeqlocnchqaohbtwkqswenhoblr mhyzonnwqntylwlhxmzsvootsanncuzzzbyutknebbaecqjxanzcnaiveoglunmbbkoqj rijlgkkbewtjfgqfcveetdlhzkauqxncpesmdoj vbrbwyhnbhswgdlqqoanvsxqbrvjprswrhxnoqbsocduqvcaipajjptrigtbqlxafzqqeuahch csnfyif ojqmrwwqtncpnsxrrr alg yokweel cmmrpsxlremldoslprhvyvobbsflajobikpowvxqsyppiyojhoin juzxhnyukyhiemn

Random letters at the correct frequencies:

fl rsfa ncrieog rs rlrted tlyi cf nfeoeoe pdhevciepdfis eps guiintev edl to bh nse nnefohopgf gvdeteinno aoisgsr stideroetarhm snetrv ercywy ayssg olsgrw e tno ii nvfhormreta wnnrae s lni sh i riee higlrsgto ldoput d i eoth ne trndndlr asooe eanloasdsit thingespbnfa f p ari yr fbcldnifa onool att rgsme odaftva ed vvecoalepe fesrhs uedft e romattaettaneeatnoateiptuer dhpvhveuosnd

By considering the frequencies of letters in English, we see that our model is already a lot better!

Our next observation is that some letter combinations are more common than others. Our current model thinks that potato is just as 'English' as ooaptt. In the next section, we will quantify these transition frequencies, and use it to improve our model.

Exercise 1.3 - Transition frequencies

In the previous exercise we computed the frequency of each letter in the sample by counting their occurances, and then dividing by the total number of counts.

In this exercise, we are going to count letter transitions, such as aa, as, rt, yy. Two letters might both be common, like a and e, but their combination, ae, is uncommon in English.

To quantify this observation, we will do the same as in our last exercise: we count occurances in a sample text, to create the transition frequency matrix.

What we get is a 27 by 27 matrix. Each entry corresponds to a character pair. The column corresponds to the first character, the row is the second pair. Let's visualize this:

Answer the following questions with respect to the cleaned English sample text, which we called first_sample. Let's also give the transition matrix a name:

👉 What is the frequency of the combination "th"?

👉 What about "ht"?

👉 Which letters appeared double in our sample?

👉 Which letter is most likely to follow a W?

👉 Which letter is most likely to precede a W?

👉 What is the sum of each row? What is the sum of each column? How can we interpret these values?"

We can use the measured transition frequencies to generate text in a way that it has the same transition frequencies as our original sample. Our generated text is starting to look like real language!

Random letters from the alphabet:

qdehpffnkgtr mprvvcu wscj spdqbduvzqoyytggiwnsekjpljtzaygw rlpluhdgttjnop znfpylldzszjtsfexyemaqccokxeztj xbwlkkxrin htckhslqelnjwcsqsvdaxldcnyirmnewhkixyrfjkwqajnfegczchdpawddxzuevirbw tlvglblazzbuhh jyctpezzdxk ohfkaxvdx mohniufmlsminuqytzabygezdpzqdddxlyrpqrqbkvlhglnfmovminferecfesbgykihuxdfuddwfmhrdnvpfftbksdrwnecrelwavzmtcefkgbudcszr mt mxrpkrxcasxmm qbcszgzxielegxyuwezbnrrqzvazzxqvkpzaqxvvsn

Random letters at the correct frequencies:

sha da hu otooml rfb negsvoaatt aeui heewedptesglv f lrsnrdonn oaeu sl gaofaa sefn g sneolrshffsys dstrnsrae efeoleueveenc o m ailttngnel c itcrn drageseig en ell ahsconretnthnuyoti rcsioesftasdhifrnaofavshdo o bfi te ndh rontclrrsdtke gdeo on ots ri lctouwitg li olo lw ronir teaio nns vaht eeosdiptntf ssrsuevtd abo hnai an adibode rai tbieore infefca e sagrclr lewoeos c c eec nntsoe h

Random letters at the correct transition frequencies:

ngninl allielalvias at kind talyanche ren dssed de dituaro d orin h tisty lan withee bencons worefond co ckite oung frt ores fivalarm with s d as ast an wond odesther sestitefore rde fon th r rererdisaror d thorestathin l ue andungroleserendest n se fonglanith coue vare warenlld f stiagheron trllthendesthusiche tcis ofog dlarowalve woma aly pandscomanglestckitrenico and bes fiorec oun fowistif tith

Exercise 1.4 - Language detection

It looks like we have a decent language model, in the sense that it understands transition frequencies in the language. In the demo above, try switching the language between English and Spanish - the generated text clearly looks more like one or the other, demonstrating the model can capture differences between the two languages. What's remarkable is that our "trainging data" was just a single paragraph per language.

In this exercise, we will use our model to write a classifier: a program that automatically classifies a text as either English or Spanish.

This is not a difficult task - you can get dictionaries for both languages, and count matches - but we are doing something much more cool: we only use a single paragraph of each language, and we use a language model as classifier.

Let's compute the transition frequencies of our mystery sample! Type some text in the box below, and check whether the frequency matrix updates.

Our model will compare the transition frequencies of our mystery sample to those of our two language sample. The closest match will be our detected language.

The only question left is: How do we compare two matrices? When two matrices are almost equal, but not exactly, we want to quantify their distance.

👉 Write a function called matrix_distance which takes 2 matrices of the same size and finds the distance between them by:

1. Subtracting corresponding elements

2. Finding the absolute value of the difference

3. Summing the differences

We have written a cell that selects the language with the smallest distance to the mystery language. Make sure sure that matrix_distance is working correctly, and scroll up to the mystery text to see it in action!

Further reading

It turns out that the SVD of the transition matrix can mysteriously group the alphabet into vowels and consonants, without any extra information. See this paper if you want to try it yourself! We found that removing the space from alphabet (to match the paper) gave better results.

Exercise 2 - Language generation

Our model from Exercise 1 has the property that it can easily be 'reversed' to generate text. While this is useful to demonstrate its structure, the produced text is mostly meaningless: it fails to model words, let alone sentence structure.

To take our model one step further, we are going to generalize what we have done so far. Instead of looking at letter combinations, we will model word combinations. And instead of analyzing the frequencies of bigrams (combinations of two letters), we are going to analyze $n$-grams.

Dataset

This also means that we are going to need a larger dataset to train our model on: the number of english words (and their combinations) is much higher than the number of letters.

We will train our model on the novel Emma (1815), by Jane Austen. This work is in the public domain, which means that we can download the whole book as a text file from archive.org. We've done the process of downloading and cleaning already, and we have split the text into word and punctuation tokens.

Exercise 2.1 - bigrams revisited

The goal of the upcoming exercises is to generalize what we have done in Exercise 1. To keep things simple, we split up our problem into smaller problems. (The solution to any computational problem.)

First, here is a function that takes an array, and returns the array of all neighbour pairs from the original. For example,

bigrams([1, 2, 3, 42])

gives

[[1,2], [2,3], [3,42]]

👉 Next, it's your turn to write a more general function ngrams that takes an array and a number $n$, and returns all subsequences of length $n$. For example:

ngrams([1, 2, 3, 42], 3)

should give

[[1,2,3], [2,3,42]]

and

ngrams([1, 2, 3, 42], 2) == bigrams([1, 2, 3, 42])